
#ifndef _TWO_WAY_LIST_H
#define _TWO_WAY_LIST_H 1

// Includes the basic TwoWayList as well as Keyify and Swapify
// (the other basic templates were removed from this file for clarity; their 
// files are included below in order to make everything backwards compatible)

/** Changelog
		
		June 5, 2009; Alin; Added iterator interface on top of the map. The iterator
		interface of the underlying TwoWayList

		June 10, 2009; Alin; Made the copy constructor and opertor= private. Subtle
		bugs appear if the default constructors generated by the compiler are used.
		It is also against the Swapping paradigm.

		June 18, 2009; Alin; Simplified the Swapify and Keyify
		templates. Now they work only if the argument has the == and =
		operator defined. This is not a limitation since all basic types have that
*/

#include <iostream>
#include "Swap.h"

// This is a template for a doubly linked list
// Type requires only the function Swap ()...
//
template <class Type>
class TwoWayList {
	
public:
	// type definitions to make our life easier
	typedef Type element;
  
	// basic constructor function
	TwoWayList ();
	
	// deconstructor function
	~TwoWayList ();
	
	// swap operator 
	void Swap (TwoWayList & List);
	
	// add to current pointer position
	void Insert (Type & Item);
	
	// add at the end of the list
	void Append (Type & Item);

	// look at the current item
	Type &Current ();
	
	// remove from current position
	void Remove (Type & Item);

	// move the current pointer position backward through the list
	void Retreat ();

	// move the current pointer position forward through the list
	void Advance ();

	// operations to check the size of both sides
	int LeftLength ();
	int RightLength ();
	int Length();
		
	// operations to consult state
	bool AtStart ();
	bool AtEnd ();

	// operations to swap the left and right sides of two lists
	void SwapLefts (TwoWayList & List); 
	void SwapRights (TwoWayList & List); 

	// operations to move the the start of end of a list
	void MoveToStart ();
	void MoveToFinish (); 

		

private:

	struct Node {
		// data
		Type data;
		Node *next;
		Node *previous;
			
		// constructor
		Node () : next (0), previous (0) {}
		~Node () {}
	};


	struct Header {
		// data
		Node * first;
		Node * last;
		Node * current;
		int leftSize;
		int rightSize;
	};

	// the list itself is pointed to by this pointer	
	Header *list;	

	// making the default constructor and = operator private so  the list
	// can only be propagated by Swap. Otherwise subtle bugs can appear
	TwoWayList(TwoWayList&);
	TwoWayList operator = (TwoWayList&);
};

// The following templates are used to quickly and easily create a
// class that wraps around a simple type (such as an int) and can be
// put into a TwoWayList or an InefficientMap.  The "Swapify" template
// attaches only a Swap operation (so a simple type can be used with
// a TwoWayList)... the "Keyify" template attaches both a Swap and an
// IsEqual (so a simple type can be used with either the TwoWayList or
// the InefficientMap).  For example, the following is valid code, which
// uses the Keyify template to attach a Swap and IsEqual to an int:
//
// void IntSwap (int &a, int &b) {
//         int temp;
//         temp = a;
//         a = b;
//         b = temp;
// }
//
// int IntCheck (int &a, int &b) {
//         return a == b;
// }
//
// int main () {
//
// 	    typedef Keyify <int, IntSwap, IntCheck> keyifiedInt;
//          InefficientMap <keyifiedInt, keyifiedInt> foo;
//          keyifiedInt bar1, bar2;
//
//          bar1 = 12;
//          bar2 = 43;
//          foo.Insert (bar1, bar2);
//          ...
//
// SPECIAL NOTE: ONLY USE THESE TEMPLATES WITH SIMPLE TYPES (ints, doubles, etc.).
// These templates maky use of the = operation, so they are only safe with such types.
// If the type is anything more complicated, then the thing to do is to create a proper
// class containing the Swap and IsEqual operations!
//
template <class Type>
	class Swapify {

	Type data;

public:

	void Swap (Swapify &withMe) {
		SWAP(data, withMe.data);
	}

	Swapify (const Type castFromMe) {
		data = castFromMe; 
	}

	operator Type() {
		return data;
	}

	Swapify () {}
	~Swapify () {}
};

template <class Type>
	class Keyify {

	Type data;

public:

	void Swap (Keyify &withMe) {
		SWAP(data, withMe.data);
	}

	Keyify (const Type castFromMe) {
		data = castFromMe; 
	}

	operator Type() {
		return data;
	}

	int IsEqual(Keyify &checkMe) {
		return data == checkMe.data;
	}

	Keyify () {}
	~Keyify () {}
};

#include "EfficientMap.h"
#include "DistributedQueue.h"

#endif
